//-----------------------------------------------------------------------------
//  Copyright (C) 2011-2018, GB Research, LLC (www.gbresearch.com)
//  
//  Boost Software License - Version 1.0 - August 17th, 2003
//
//  Permission is hereby granted, free of charge, to any person or organization
//  obtaining a copy of the software and accompanying documentation covered by
//  this license (the "Software") to use, reproduce, display, distribute,
//  execute, and transmit the Software, and to prepare derivative works of the
//  Software, and to permit third-parties to whom the Software is furnished to
//  do so, all subject to the following:
//
//  The copyright notices in the Software and this entire statement, including
//  the above license grant, this restriction and the following disclaimer,
//  must be included in all copies of the Software, in whole or in part, and
//  all derivative works of the Software, unless such copies or derivative
//  works are solely in the form of machine-executable object code generated by
//  a source language processor.
//
//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//  FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
//  SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
//  FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
//  ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
//  DEALINGS IN THE SOFTWARE.
//-----------------------------------------------------------------------------

#pragma once

#include <type_traits>
#include <vector>
#include <assert.h>

#include "axe_exception.h"
#include "axe_trait.h"

namespace axe
{
    //-------------------------------------------------------------------------
    // iterator pair
    //-------------------------------------------------------------------------
    template<class I>
    struct it_pair
    {
    private:
        I begin_;
        I end_;
    public:
        it_pair() = default;
        it_pair(I b, I e) : begin_(b), end_(e) {}
        
        template<class T, class = std::void_t<decltype(std::begin(std::declval<T>()), std::end(std::declval<T>()))>>
        explicit it_pair(T&& s) : begin_(std::begin(std::forward<T>(s))), end_(std::end(std::forward<T>(s))) {}

        constexpr I begin() const { return begin_; }
        constexpr I cbegin() const { return begin_; }
        constexpr I end() const { return end_; }
        constexpr I cend() const { return end_; }
        it_pair& next() { begin_ = std::next(begin_); return *this; }
        constexpr bool empty() const { return begin_ == end_; }
        constexpr auto size() const { return std::distance(begin_, end_); }
    };

    template<class T>
    explicit it_pair(T&& s)->it_pair<decltype(std::begin(std::forward<T>(s)))>;
    
    template<class I>
    it_pair(I, I)->it_pair<I>;

    //-------------------------------------------------------------------------
    template<class I, class R>
    constexpr const bool is_extracting_rule_v = takes_args_v< std::decay_t<R>, it_pair<I>>;

    //-------------------------------------------------------------------------
    // skips characters which satisfy F (either predicate or rule)
    //-------------------------------------------------------------------------
    template<class I, class F>
    class skip_iterator
    {
        static_assert(is_input_iterator<I>);
        static_assert(std::is_copy_constructible_v<F>);
        static_assert(std::is_copy_constructible_v<I>);
        I begin_;
        I end_;
        F fun_;

        void inc(I& it) const
        {
            if (it != end_) ++it;
            skip(it);
        }

        void advance(I& it, size_t dist) const
        {
            for (; it != end_ && dist > 0; --dist)
                inc(it);
        }

        // skipper with predicate
        template<class Pred>
        std::enable_if_t<!AXE_IS_RULE(Pred)>
            skip(const Pred& p, I& it) const
        {
            for (; it != end_ && p(*it); ++it);
        }

        // skipper with rule
        template<class Rule>
        std::enable_if_t<AXE_IS_RULE(Rule)>
            skip(const Rule& r, I& it) const
        {
            while (it != end_)
            {
                auto match = r(it, end_);
                if (match.matched)
                    it = match.position;
                else
                    return;
            }
        }

        void skip(I& it) const { skip(fun_, it); }

    public:
        using iterator_category = std::conditional_t< is_forward_iterator<I>, std::forward_iterator_tag, std::input_iterator_tag>;
        using difference_type = typename std::iterator_traits<I>::difference_type;
        using value_type = typename std::iterator_traits<I>::value_type;
        using pointer = typename std::iterator_traits<I>::pointer;
        using reference = typename std::iterator_traits<I>::reference;

        skip_iterator() = default;
        
        template<class Fun>
        skip_iterator(I begin, I end, Fun&& fun) : begin_(begin), end_(end), fun_(std::forward<Fun>(fun))
        {
            skip(begin_);
        }

        skip_iterator(const skip_iterator&) = default;

        I get() const { return begin_; }
        bool empty() const { return begin_ == end_; }
        
        auto& operator++ () { inc(begin_); return *this; }
        auto operator++ (int) { auto tmp = *this; inc(begin_); return tmp; }
        auto operator+ (size_t dist) const
        {
            auto tmp = *this;
            tmp.advance(tmp.begin_, dist);
            return tmp;
        }

        decltype(auto) operator* () const { return *begin_; }
        decltype(auto) operator->() const { return begin_.operator->(); }
        bool operator== (const skip_iterator& other) const { return begin_ == other.begin_; }
        bool operator!= (const skip_iterator& other) const { return !operator==(other); }
        auto& operator= (const skip_iterator& i) { begin_ = i.begin_; return *this; }
        auto& operator= (skip_iterator&& i) { begin_ = std::move(i.begin_); return *this; }
    };

    template<class I, class Fun>
    skip_iterator(I, I, Fun&&)->skip_iterator<I, std::decay_t<Fun>>;


    //-------------------------------------------------------------------------
    // skips characters which satisfy F (either predicate or rule)
    //-------------------------------------------------------------------------
    template<class I, class F>
    class skip_it_pair
    {
        I begin_{};
        I end_{};
        F fun_{};
        friend class iterator;

        void inc(I& it) const
        {
            if(it != end_) ++it;
            skip(it);
        }
        void advance(I& it, size_t dist) const
        {
            for(; it != end_ && dist > 0; --dist)
                inc(it);
        }

        // skipper with predicate
        template<class Pred>
        std::enable_if_t<!AXE_IS_RULE(Pred)>
            skip(const Pred& p, I& it) const
        {
            for(; it != end_ && p(*it); ++it);
        }

        // skipper with rule
        template<class Rule>
        std::enable_if_t<AXE_IS_RULE(Rule)>
            skip(const Rule& r, I& it) const
        {
            while(it != end_)
            {
                auto match = r(it, end_);
                if(match.matched)
                    it = match.position;
                else
                    return;
            }
        }

        void skip(I& it) const { skip(fun_, it); }

        // skip iterator class
        class iterator
        {
            union
            {
                bool invalid;
                std::reference_wrapper<const skip_it_pair> ip_;
            };
            I it_;
        public:
            typedef typename I::reference       reference;
            typedef typename I::value_type      value_type;
            typedef typename I::difference_type difference_type;
            typedef typename I::pointer         pointer;
            typedef std::forward_iterator_tag   iterator_category;

            iterator() : invalid(true) {}
            iterator(const skip_it_pair& ip, I it) : ip_(ip), it_(it) {}
            iterator& operator++ () { ip_.get().inc(it_); return *this; }
            iterator operator++ (int) { auto tmp = *this; ip_().get().inc(it_); return tmp; }
            iterator operator+ (size_t dist) const
            {
                auto tmp = *this;
                tmp.ip_.advance(tmp.it_, dist);
                return tmp;
            }
            operator I () const { return it_; }

            reference operator* () const { return *it_; }
            pointer operator->() const { return it_.operator->(); }
            bool operator== (const iterator& other) const { return it_ == other.it_; }
            bool operator!= (const iterator& other) const { return !operator==(other); }
            iterator& operator= (const iterator& i) { ip_ = i.ip_;  it_ = i.it_; return *this; }

            I get() const { return it_; }
        };
    public:
        skip_it_pair() = default;
        template<class Fun>
        skip_it_pair(I begin, I end, Fun&& fun) : begin_(begin), end_(end), fun_(std::forward<Fun>(fun))
        {
            skip(begin_);
        }
        iterator begin() const { return iterator(*this, begin_); }
        iterator end() const { return iterator(*this, end_); }
    };

    template<class I, class F>
    inline skip_it_pair<I, std::decay_t<F>> make_skip_it_pair(I begin, I end, F&& f)
    {
        return skip_it_pair<I, std::decay_t<F>>(begin, end, std::forward<F>(f));
    }

    //-------------------------------------------------------------------------
    // converting iterator
    //-------------------------------------------------------------------------
    template<class I, class F>
    class convert_iterator
    {
        I it_;
        F fun_;
        friend class iterator;
    public:
        using reference = typename I::reference;
        using value_type = typename I::value_type;
        using difference_type = typename I::difference_type;
        using pointer = typename I::pointer;
        using iterator_category = std::forward_iterator_tag;

        convert_iterator(I it, F fun) : it_(it), fun_(std::move(fun)) {}
        convert_iterator& operator++ () { ++it_; return *this; }
        convert_iterator operator++ (int) { auto tmp = *this; ++it_; return tmp; }
        value_type operator* () const
        {
            static_assert(std::is_convertible<decltype(fun_(*it_)), value_type>::value,
                "Function return type must be convertible to value_type");
            return fun_(*it_);
        }

        bool operator== (const convert_iterator& other) const { return it_ == other.it_; }
        bool operator!= (const convert_iterator& other) const { return !operator==(other); }
        convert_iterator& operator= (const convert_iterator& i) { it_ = i.it_; fun_ = i.fun_; return *this; }
        I get() const { return it_; }
    };

    //-------------------------------------------------------------------------
    template<class I, template<class, class> class C = std::vector, class A = std::allocator<typename I::value_type>>
    class input_buffer
    {
        friend class iterator;
        I it_; // always points to position that hasn't been read
        I end_;
        C<typename I::value_type, A> buffer_;

        bool read_from_input()
        {
            if(it_ != end_)
            {
                buffer_.push_back(*it_);
                ++it_;
                return true;
            }
            return false;
        }
        bool valid(size_t position) const { return position != size_t(-1); }
        bool sync(size_t position)
        {   // reads data upto 'position' if necessary
            bool success = valid(position);

            if(position > buffer_.size())
                for(size_t dist = position - buffer_.size(); dist && success; --dist)
                    success = read_from_input();

            return success;
        }

        void inc(size_t& position)
        {
            if(valid(position) && sync(position + 1))
            {
                ++position;
                if(position == buffer_.size() && it_ == end_)
                    position = -1;
            }
            else
                position = -1;
        }

        typename I::reference get_ref(size_t position)
        {
            if(position >= buffer_.size() && (!sync(position) || !read_from_input()))
                throw_failure("input_buffer: dereferencing end iterator");
            return buffer_[position];
        }

        I get_iter(size_t position) const
        {
            if(valid(position) && position != buffer_.size())
                throw_failure("input_buffer: rollback not possible");
            return it_;
        }

    public:
        input_buffer(I begin, I end) : it_(begin), end_(end) {}

        class iterator
        {
            input_buffer&   buf_;
            size_t          position_;
        public:
            typedef typename I::reference       reference;
            typedef typename I::value_type      value_type;
            typedef typename I::difference_type difference_type;
            typedef typename I::pointer         pointer;
            typedef std::forward_iterator_tag   iterator_category;

            iterator(input_buffer& buf, size_t position) : buf_(buf), position_(position) {}

            iterator& operator++ () { buf_.inc(position_); return *this; }
            iterator operator++ (int) { auto tmp = *this; buf_.inc(position_); return tmp; }

            reference operator* () const { return buf_.get_ref(position_); }
            bool operator== (const iterator& other) const { return &buf_ == &other.buf_ && position_ == other.position_; }
            bool operator!= (const iterator& other) const { return !operator==(other); }
            iterator& operator= (const iterator& i) { assert(&buf_ == &i.buf_); position_ = i.position_; return *this; }

            I get() const { return buf_.get_iter(position_); }
        };

        iterator begin() { return iterator(*this, 0); }
        iterator end() { return iterator(*this, -1); }
    };

}
